/*
题目：二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度
https://leetcode.cn/problems/maximum-width-of-binary-tree/
 */
public class WidthOfBinaryTree {
    //这个二叉树可以看成完全二叉树，设某个节点下标为k，则左节点2k，右节点2k+1，则当层宽度为最右边下标-最左边下标 + 1
    public int widthOfBinaryTree(TreeNode root) {
        Queue<AnnotatedNode> queue = new LinkedList<> ();
        int ans = 1;//记录答案
        queue.offer(new AnnotatedNode(root,1,1));//深度1，下标1

        while (!queue.isEmpty()) {
            int curSize = queue.size();
            int curDepth = 0;
            int leftIndex = 0;
            
            while (curSize != 0) {
                AnnotatedNode cur = queue.poll();
                if (cur.node.left != null) {
                    queue.offer(new AnnotatedNode(cur.node.left, cur.depth + 1, 2 * cur.index));
                }
                if (cur.node.right != null) {
                    queue.offer(new AnnotatedNode(cur.node.right, cur.depth + 1, 2 * cur.index + 1));
                }
                if (curDepth != cur.depth) {//记录当层第一个节点的下标
                    curDepth = cur.depth;
                    leftIndex = cur.index;
                }
                curSize--;
                ans = Math.max(ans, cur.index - leftIndex + 1);
            }
        }

        return ans;
    }

    //记录数据的节点
    class AnnotatedNode {
        TreeNode node;//题意节点
        int depth;//深度
        int index;//下标
        public AnnotatedNode(TreeNode node, int depth, int index) {
            this.node = node;
            this.depth = depth;
            this.index = index;
        }
    }
}
